1. Field of Invention
The systems and methods of the invention concern information directed routing in ad hoc sensor networks.
2. Description of Related Art
Routing in traditional communications networks is a well-studied problem in both patent and non-patent literature. Graph-based algorithms such as Dijkstra's or Bellman-Ford type algorithms are often used to determine optimal paths within a network with respect to metrics such as, for example, communication cost and delay. Of recent interest is the topic of routing with resource constraints. Energy aware network routing has been proposed in various places, such as, Shah et al., Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Mar. 17-21, 2002, Orlando, Fla.; and Aslam et al., Proceedings of the Seventh Annual International Conference on Mobile Computing and Networking (Mobicom), July 2001, Rome, Italy. More complicated constraints are incorporated into routing problems in U.S. Provisional Patent Application Ser. No. 60/373,916, entitled, “Systems and methods for constrained anisotropic diffusion routing with an ad hoc network,” by Haussecker, et al., and co-pending U.S. non-provisional patent application Ser. No. 10/446,115, the disclosures of which are hereby incorporated by reference in their entirety. In Haussecker et al., the route destination is specified by a set of constraints, and the disclosed algorithm seeks efficient routes to the destination.
Constrained anisotropic diffusion routing (CADR) is proposed in the target tracking applications of Haussecker et al. to route a query from a peripheral access point to high activity regions, using information gained enroute to guide the successor node selection. The information gained enroute is measured using variations of distance metric, assuming the sensors that are close by the target have more information about the target than those that are far away from the target. The optimization problem is greedy, that is, at each step, the current leader selects among its successors the best choice for the time being and hands over leadership to the best choice. Due to its greedy nature, the selection is sub-optimal and often gets stuck at sensor holes where the sensor field is sparse.
Network route selection for fixed centralized computer networks is described in a number of publications, including, for example, U.S. Pat. No. 6,321,271, which describes a method for finding the short routing path under some acceptable delay constraints. The method described by this patent employs a two stage process, using Dijkstra's algorithm at each phase. The algorithm is designed for wired high speed data communication networks, is centralized in nature, and requires complete knowledge of network topology in some central unit.
U.S. Pat. No. 6,078,963 describes a distributive router system. The focus of the disclosure of this patent is on the infra-structure. The router mechanism described by this patent is determined prior to the system setup.
U.S. Pat. No. 6,363,319 describes a method and apparatus for selecting a route for a flow from a plurality of network paths connecting a source to a destination. The accumulative cost is determined dynamically based on network characterizations such as flow attributes such as, for example, priority, bandwidth demand, etc., and path attributes, such as for example, available bandwidth.
U.S. Pat. No. 6,421,354 describes a system for providing data acquisition services for a customer from a sensor located in a remote location. The focus of the disclosure of the patent is on infra-structure.
U.S. Provisional Patent Application Ser. No. 60/373,916, discussed above, describes a method that uses information gained in a greedy algorithm to select the next sensor.